Walk

Memory limit: 256 MB

The names of towns in Byteotia are unique sequences of exactly bits. There are towns in Byteotia, and thus, only sequences of bits do not correspond to any town.

Some pairs of towns are connected with roads. Specifically, two towns are directly linked by a road if and only if their names differ in a single bit. The roads do not cross outside of towns.

Byteasar intends to take a stroll - he intends to walk from the town to the town , taking the existing roads. Your task is to write a program that will determine if such a walk is possible.

Input

In the first line of the standard input, there are two integers, and (, , , ), separated by a single space. These are the length of town names in bits and the the number of -bit sequences that do not correspond to any town, respectively. In the second line, there are two strings, separated by a single space, each consisting of characters 0 and/or 1. These are the names of the towns and . In the lines that follow, all the sequences of bits that do not correspond to any town are given, one sequence per line. Each such sequence is a string of characters 0 and/or 1. You may assume that and are not among those sequences.

In tests worth 25% of total points the additional condition holds.

Output

Your program should print to the standard output the word TAK (Polish for yes) if walking from the town to the town is possible, and the word NIE (Polish for no) otherwise.

Example

For the input data:

4 6
0000 1011
0110
0111
0011
1101
1010
1001

the correct result is:

TAK

For the input data:

2 2
00 11
01
10

the correct result is:

NIE

Explanation of the first example: The following are two examples of a walk from 0000 to 1011:

• 
• .

Sample grading tests:

• 1ocen: , , a name corresponds to a town if and only if it is not divisible by 5, intended walk is from to ; answer NIE;
• 2ocen: , , the towns and are directly linked by a road; answer TAK;
• 3ocen: a nice test with ; answer TAK.

Task author: Wojciech Rytter